class Solution:
	# @param {integer} x
	# @return {integer}
	def mySqrt(self, x):
		if x in [0,1]:
			return x
		i, j = 0, x
		while j > i + 1:
			mid = (i + j) / 2
			m = mid*mid
			if m == x:
				return mid
			if m - x < 0:
				i = mid
			else:
				j = mid
		return i

if __name__ == '__main__':
	for i in range(20):
 		print Solution().mySqrt(i), 

